﻿#pragma once
#include<vector>
namespace CLOSE_HASH
{ 
enum State
{
	EMPTY,
	EXIST,
	DELETE,
};
template<class T>
struct HashData
{
	T _data;
	State _state;
};
template<class K,class T,class KOfT>
class HashTable
{
	typedef HashData<T> HashData;
public:

	bool Insert(const T& d)
	{
		KOfT koft;
		size_t sz = _tables.size();
		//负载因子=数据/表的大小
		/*二次探测负载因子*/if (sz == 0 || _num * 10 / sz >= 5)
		///*线性探测负载因子*/if (sz == 0 || _num * 10 / sz >= 7)
		{
			//增容（空间开二倍，旧表重新映射新表，释放旧表空间）
			// 1.原始写法
		/*	size_t newsize = sz == 0 ? 10 : 2 * sz;
			vector<HashData> newtables;
			newtables.resize(newsize);
			for (size_t i = 0;i < sz;++i)
			{
				if (_tables[i]._state == EXIST)
				{
					size_t newindex = koft(_tables[i]._data) % newtables.size();
					while (newtables[newindex]._state == EXIST)
					{
						++newindex;
						if (newindex == newtables.size())
						{
							newindex = 0;
						}
					}
					newtables[newindex] = _tables[i];
				}
			}
			_tables.swap(newtables);*/
			
			// 2.复用写法
			HashTable<K,T,KOfT> newht;
			size_t newsize=sz == 0 ? 10 : 2 * sz;
			newht._tables.resize(newsize);
			for (size_t i = 0;i < sz;++i)
			{
				if (_tables[i]._state == EXIST)
				{
					newht.Insert(_tables[i]._data);
				}
			}
			_tables.swap(newht._tables);
		}
		//1.计算位置

		//线性探测
		/*size_t index = koft(d) % _tables.size();
		while (_tables[index]._state == EXIST)
		{
			if (koft(_tables[index]._data)== koft(d))
			{
				return false;
			}
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}*/

		//二次探测
		size_t index_0 = koft(d) % _tables.size();
		size_t index = index_0, i = 1;
		while (_tables[index]._state == EXIST)
		{
			if (koft(_tables[index]._data) == koft(d))
			{
				return false;
			}
			index=(index_0+i*i)% (_tables.size());
			++i;
		}
		//2.插入
		_tables[index]._data = d;
		_tables[index]._state = EXIST;
		_num++;
		return true;

	}
	HashData* Find(const T& key)
	{
		KOfT koft;
		//1.计算位置

		//线性探测
	/*	size_t index = koft(key) % _tables.size();
		while (_tables[index]._state != EMPTY)
		{
			if (koft(_tables[index]._data) == koft(key))
			{
				if (_tables[index]._state == EXIST)
				{
					return &_tables[index];
				}
				else if (_tables[index]._state == DELETE)
					return nullptr;     
			}
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}*/

		//二次探测
		size_t index_0 = koft(key) % _tables.size();
		size_t index = index_0, i = 1;
		while (_tables[index]._state == EXIST)
		{
			if (koft(_tables[index]._data) == koft(key))
			{
				if (_tables[index]._state == EXIST)
				{
					return &_tables[index];
				}
				else if (_tables[index]._state == DELETE)
					return nullptr;
			}
			index = (index_0 + i * i) % (_tables.size());
			++i;
		}
		return nullptr;
	}
	bool Erase(const T& key)
	{
		HashData* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_num;
			return true;
		}
		else
		{
			return false;
		}
	}

private:
	vector<HashData> _tables;
	size_t _num=0;
};

template<class K>
struct SetKeyOfT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};
/*测试用例*/void TestHashTable_Closed()
{
	cout << "****HashTable_Closed测试用例开始****" << endl;
	HashTable<int, int, SetKeyOfT<int>> ht;
	ht.Insert(12);
	ht.Insert(24);
	ht.Insert(15);
	ht.Insert(6);
	ht.Insert(18);
	ht.Insert(25);
	ht.Insert(22);
	ht.Insert(78);

	cout << "****HashTable_Closed测试用例结束****" << endl << endl;
}
}

namespace OPEN_HASH
{
	template<class T>
	struct HashNode
	{
		HashNode(const T& data = T()) :_data(data), _next(nullptr)
		{ }
		T _data;
		HashNode<T>* _next;
	};
	template<class K, class T, class KOfT>
	struct __HashTableIterator
	{
		typedef HashNode<T> Node;
		Node* node;
	};

	template<class K, class T, class KOfT>
	class HashTable
	{
		typedef HashNode<T> Node;
	public:
		bool Insert(const T& data)
		{
			KOfT koft;
			size_t sz = _tables.size();
			if (_tables.size() == _nums)
			{
				vector<Node*> newtables;
				size_t newsize = sz == 0 ? 10 : sz * 2;
				newtables.resize(newsize);
				for (size_t i = 0;i < sz;++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t newindex = koft(cur->_data) % newtables.size();
						cur->_next = newtables[newindex];
						newtables[newindex] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			size_t index = koft(data) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == koft(data))
				{
					return false;
				}
				else
				{
					cur = cur->_next;
				}
			}
			Node* newnode = new Node(data);
			newnode->_next = _tables[index];
			_tables[index]=newnode;
			_nums++;
		}
		Node* Find(const K& key)
		{
			KOfT koft;
			size_t sz = _tables.size(); 
			size_t index = key % sz;
			Node* cur = _tables[index];
			while (cur)
			{
				if(koft(cur->_data)==koft(key))
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			KOfT koft;
			size_t sz = _tables.size();
			size_t index = key % sz;
			Node* cur = _tables[index];
			Node* prev=nullptr;
			while (cur)
			{
				if (koft(cur->_data) == koft(key))
				{
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
		}
	private:
		vector<Node*>_tables;
		size_t _nums=0;
	};
	template<class K>
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	/*测试用例*/void TestHashTable_Open()
	{
		cout << "****HashTable_Open测试用例开始****" << endl;
		HashTable<int, int, SetKeyOfT<int>> ht;
		ht.Insert(12);
		ht.Insert(24);
		ht.Insert(15);
		ht.Insert(6);
		ht.Insert(18);
		ht.Insert(25);
		ht.Insert(22);
		ht.Insert(78);

		cout << "****HashTable_Open测试用例结束****" << endl << endl;
	}
}